1. Field of the Invention
This invention relates to searchable database applications and, more particularly, to circuits and methods for locating and extracting a plurality of matching entries by comparing variations of a single search key to a database of entries.
2. Description of the Related Art
The following descriptions and examples are not admitted to be prior art by virtue of their inclusion within this section.
A communication network is generally recognized as an interconnection of forwarding devices that process and send packets of information across the network. The network can either be an Internet or an Intranet and the forwarding devices can be gateways, bridges, switches, or routers. One objective of the forwarding devices is to reliably forward the packets from a source to a destination.
In whatever form, a forwarding device typically includes one or more lookup tables. An incoming destination address (or other search key) is derived from a packet of information and compared against entries stored within the lookup table. Resulting from the search, the associated packet of information may be processed according to a set of rules and sent to an appropriate output port of the forwarding device. As links of the network change, routing protocols exchange information among the forwarding devices in order to change the entries stored within the corresponding lookup tables. This change will modify not only the entries within the lookup table, but also the next-hop identifiers or other associated data pointed to by the addresses of those entries. Routing through the forwarding devices can, therefore, be changed dynamically as links go down and come back up in various parts of the Internet or Intranet.
A popular implementation of the lookup table involves content-addressable memory (CAM) device. One important feature of a CAM is that fairly fast searches can be undertaken of any database, list, pattern, image, or voice-recognition data stored within a computer or a component within a communications network. For example, memory searches can be quickly performed in a CAM by comparing a search key against each of the CAM entries in parallel. As a result, CAM devices are often employed in network equipment (e.g., forwarding devices), computer systems and other devices that benefit from rapid content searching.
To enable rapid searching, CAMs are often organized differently than other memory devices (e.g., a random access memory, or RAM). In a RAM, for example, data is stored in a particular location, called an address. When conducting a memory search within a RAM, the address of a memory location is supplied to retrieve the data stored in that memory location. In a CAM, however, data is often stored in a random fashion. The locations at which data is stored within a CAM can be arbitrary. For example, the locations may be selected by an address, or the data may simply be written into the first available memory location. Once data is stored in a CAM, the stored data can be found by comparing all of the CAM entries with input data (i.e., a search key) placed in a comparand register. When the content stored in a CAM memory location does not match the data placed in the comparand register, the CAM device returns a “no match” indication. If a match is found, however, the CAM device returns a “match” indication by asserting the match line for that entry. The CAM device will also return the address of the memory location in which the matching data is stored. A CAM thereby operates opposite that of a conventional memory device by receiving data, and returning a matching CAM index, address, or location.
For every CAM entry that matches the data in the comparand register, a corresponding match line will be asserted to indicate a match condition. If the data in the comparand register matches more than one CAM entry, the match lines corresponding to each of the matching CAM entries are asserted, along with a “multiple match” flag to indicate a multiple match condition. The match line signals from each CAM block are combined in a priority encoder to determine the address of the highest-priority matching CAM entry. In some cases, the highest-priority matching entry may be the “longest-matching prefix entry,” or the CAM entry containing the greatest number of most significant bits matching the search key. In any case, the address of the highest-priority matching entry (i.e., the CAM index) may be extracted from the CAM and forwarded to a memory location (specified by the CAM index) of an associated memory device. The associated memory device (e.g., an associated RAM device) may then direct the packet of information to an appropriate output port of the forwarding device.
Though various methods have been devised for detecting multiple match conditions, no methods currently exist for easily extracting a potentially unlimited number of entries matching a single search key. In some cases, a valid bit may be stored within each of the CAM entries. The valid bit may be set for each valid entry in the CAM (i.e., each memory location containing useful stored data) so that only the valid CAM entries will be searched. In order to extract multiple matching entries from the CAM, a first matching entry must be invalidated (to exclude that entry from further searches) before the search key is re-issued to find a next matching entry. Though multiple matching entries may be found in this manner, it is undesirably slow and cannot be implemented within multi-threaded systems (such as today's packet processors), which require multiple threads to have simultaneous access to the CAM device.
To accommodate multi-threaded systems, the above method may utilize a plurality of valid bits per CAM entry, one for every thread sharing the CAM device. However, the number of valid bits needed is directly proportional to the number of threads requiring simultaneous access to the CAM device. Though conventional methods may include up to 8 valid bits for supporting up to 8 threads, they cannot provide a viable solution for many of today's multi-threaded packet processors, which may contain between 32 and 128 threads. Since each CAM entry contains a fixed number of bits (e.g., about 72 to 576 bits or more), allocating an increasing number of those bits to a valid bit field may ultimately prevent any data from being stored within the CAM entries.
Therefore, a need exists for an improved method for extracting a potentially unlimited number of CAM entries matching a single search key. The improved method may be used in modern applications, which require ‘k’ matches, the first ‘k’ matches or all entries matching a particular search key to be extracted from a CAM device. Unlike conventional methods, the improved method may be equally applied to single-threaded systems and multi-threaded systems with substantially any number of threads.